package top.humbleyuan.backtrack;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 20:11
 * @Des 搜索单词
 * @pro 代码需要优化
 */
public class LeetCode_79 {
    public static void main(String[] args) {
        Character[][] cha = { {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}};
        String key = "ABCCED";
        String cur = "";

        int[][] begin = new int[1][2];
        boolean[][] f = new boolean[cha.length][cha[0].length];

        for (int i = 0; i < cha.length; i++) {
            for (int j = 0; j < cha[0].length; j++) {

                /**
                 * 首个字符判定，后面可以优化到dfs一起
                 */
                begin[0][0] = i;
                begin[0][1] = j;
                cur += cha[i][j];

                if (cur.equals(key)) {
                    System.out.println("true");
                    return;
                }

                // 剪枝
                if (!cur.equals(key.substring(0, cur.length()))) {
                    continue;
                }

                f[i][j] = true;
                if (leet_79_dfs(key, cha, begin,
                        f, cur)) {
                    System.out.println("true");
                    return;
                }

                cur = "";
                f = new boolean[cha.length][cha[0].length];
            }
        }
    }

    public static boolean leet_79_dfs(String key, Character[][] cha, int[][] curPoint, boolean[][] exist, String cur) {
        int rowIndex;
        int colIndex;

        // curPoint可以往上下左右四个方向
        for (int i = 0; i < 4; i++) {
            switch (i) {
                case 0:
                    curPoint[0][0] += 1;
                    break;
                case 1:
                    curPoint[0][0] -= 1;
                    break;
                case 2:
                    curPoint[0][1] += 1;
                    break;
                case 3:
                    curPoint[0][1] -= 1;
                    break;
            }

            rowIndex = curPoint[0][0];
            colIndex = curPoint[0][1];
            // 剪枝
            if(!(rowIndex >= 0 && rowIndex < cha.length) ||
                    !(colIndex >= 0 && colIndex < cha[0].length) || exist[rowIndex][colIndex]) {

            } else {
                cur += cha[rowIndex][colIndex];

                // 剪枝
                if(!cur.equals(key.substring(0, cur.length()))) {
                    cur = cur.substring(0, cur.length() - 1);
                } else {
                    //System.out.println(cur);
                    exist[rowIndex][colIndex] = true;
                    if(cur.equals(key) || leet_79_dfs(key, cha, curPoint, exist, cur)) {
                        return true;
                    }
                    cur = cur.substring(0, cur.length() - 1);
                    exist[rowIndex][colIndex] = false;
                }

            }

            // 回溯
            switch (i) {
                case 0:
                    curPoint[0][0] -= 1;
                    break;
                case 1:
                    curPoint[0][0] += 1;
                    break;
                case 2:
                    curPoint[0][1] -= 1;
                    break;
                case 3:
                    curPoint[0][1] += 1;
                    break;
            }
        }

        return false;

    }
}
